#include "StdAfx.h"
#include "MaximumPalindromeScore.h"


MaximumPalindromeScore::MaximumPalindromeScore(void)
{
}

MaximumPalindromeScore::~MaximumPalindromeScore(void)
{
}

int MaximumPalindromeScore::maximize(std::string word, int maxChanges)
{
	if (word.size() < 1 || word.size() > 50)
		return -1;
	for (unsigned int i = 0; i < word.size(); i++) {
		if (word[i] < 97 || word[i] > 122)
			return -1;
	}
	if (maxChanges < 0 || maxChanges > 50)
		return -1;

	int K = 0;
	int maxDiffers;
	bool changable = false;
	int startIdx = 0, endIdx = word.size() - 1;
	while (true) {
		if (changable) {
			maxDiffers = 0;
		} else {
			maxDiffers = calcDiffers(word, startIdx, endIdx);
		}
		if (maxDiffers == 0) {
			// A palindrome string
			if ((endIdx + 1) % 2 == 0) {
				K = K + 1;
				startIdx = 0; 
				endIdx = endIdx / 2;
				// And this time we should recalc the differs
				changable = false;
				continue;
			} else {
				K = K + 1;
				break;
			}
		} else {
			// Not a palindrome string
			if (maxDiffers <= maxChanges) {
				// Could make a palindrome string
				changable = true;
				// TODO: How to make changes?
				if (word.size() % 2 == 0) {
					maxChanges -= maxDiffers;
					makeChanges(&word);
				}
				continue;
			} else {
				// Can't make
				break;
			}
		}

	}

	return K;
}

int MaximumPalindromeScore::calcDiffers(std::string word)
{
	int startIdx, endIdx, maxDiffers = 0;

	startIdx = 0;
	endIdx = word.size() - 1;
	while (true) {
		if (startIdx >= endIdx){
			break;
		}
		if (word[startIdx] != word[endIdx]) {
			maxDiffers++;
		}
		startIdx++;
		endIdx--;
	}
	return maxDiffers;
}

int MaximumPalindromeScore::calcDiffers(std::string word, int startIdx, int endIdx)
{
	int maxDiffers = 0;
	while (true) {
		if (startIdx >= endIdx){
			break;
		}
		if (word[startIdx] != word[endIdx]) {
			maxDiffers++;
		}
		startIdx++;
	    endIdx--;
	}
	return maxDiffers;
}

void MaximumPalindromeScore::makeChanges(std::string* word)
{
	// First find indices 
	int startIdx, endIdx;
	int *differIndices = new int[word->size() / 2];
	unsigned int i;
	for (i = 0; i < word->size() / 2; i++) {
		differIndices[i] = -1;
	}
	int differIndex = 0;
	startIdx = 0;
	endIdx = word->size() - 1;
	while (true) {
		if (startIdx >= endIdx){
			break;
		}
		if ((*word)[startIdx] != (*word)[endIdx]) {
			differIndices[differIndex++] = startIdx;
		}
		startIdx++;
	    endIdx--;
	}

	// Then make changes
	int halfSize = word->size() / 2;
	int lastIdx = word->size() - 1;
	for (i = 0; i < word->size() / 2; i++) {
		if (differIndices[i] != -1) {
			if ((*word)[differIndices[i]] == (*word)[halfSize - differIndices[i] - 1]
			|| (*word)[differIndices[i]] == (*word)[halfSize + differIndices[i]]) {
				(*word)[lastIdx - differIndices[i]] = (*word)[differIndices[i]];
			} else if ((*word)[lastIdx - differIndices[i]] == (*word)[halfSize + differIndices[i]]
			|| (*word)[lastIdx - differIndices[i]] == (*word)[halfSize - differIndices[i] - 1]) {
				(*word)[differIndices[i]] = (*word)[lastIdx - differIndices[i]];				
			} else {
				(*word)[lastIdx - differIndices[i]] = (*word)[differIndices[i]];
			}
		}
	}
	
}